package com.sicheng.lc.lc笔试.腾讯篇;

import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/4/25 18:01
 */
public class 股票买卖 {
    /**
     * 5.股票买卖
     * 给定n天以及初始资产m，然后输入一个数组表示每天股票价格。
     * 一条只能买或卖1只股，但是可以无限持股，不能贷款即资产必须≥0。
     * 问你到最后一天的时候最大资产是多少，资产总数为[现金 + 持股数 * 股票价格]
     * <p>
     * 例如
     * 6 2
     * 2 3 1 1 1 2
     * 第一天买入，第二天卖出，第3,4,5天买入，最后一天就有2*3 = 6的总资产。
     * 链接：https://leetcode-cn.com/circle/discuss/JwMjS8/view/mXLSyh/
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        int[] prices = new int[n];
        for (int i = 0; i < n; i++) {
            prices[i] = scanner.nextInt();
        }
        int[][] dp = new int[n][n];

        // dp[i][j] 第i天持有j股的现金剩余最大值

        for (int j = 0; j < dp.length; j++) {
            for (int i = 0; i < dp.length; i++) {
                dp[i][j] = Integer.MIN_VALUE >> 1;
            }
        }
        dp[0][0] = m;
        dp[0][1] = m - prices[0];
        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j < dp.length; j++) {
                if (j == 0) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j + 1] + prices[i]);
                } else {
                    dp[i][j] = Math.max(Math.max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]), dp[i - 1][j + 1] + prices[i]);
                    if (dp[i][j] <= 0) {
                        break;
                    }
                }
            }
        }
        int max = 0;
        for (int i = 0; i < n; i++) {
            max = Math.max(dp[n - 1][i] + i * prices[i], max);
            if (dp[n - 1][i] < 0)
                break;
        }
        System.out.println(max);
    }

}
